A known algorithm used for the correction of errors when data is transmitted in a noisy environment is known as turbo-decoding. In turbo-decoding, data bits to be transmitted are divided into block, and for each block, special bits are added and transmitted along with the data bits. The special bits that are added to each block enable the recovery of the original data, which is most beneficial in situations where the transmission is prone to noise that can corrupt the data when transmitted. The basic concepts involved in turbo-decoding are described, for example in Berrou, C., Glavieux, A. and Thitimajshima, P., Near Shannon Limit Error-Correcting Coding and Decoding: Turbo Codes, ICC, pp 1064-1070, 1993; and Berrou, C et. al., Turbo Codes: General Principles and Applications, Proceedings of the 6th Tierrenia International Workshop of Digital Communications, Tierrenia, Italy, September 1993, as well as in U.S. Pat. No. 5,446,747, all of which are incorporated herein by reference for all purposes.
The basic operation of a conventional turbo-decoder is discussed at length in the references mentioned above. Each of the conventional methods related to turbo-decoding discussed in the references mentioned above is based on several iterations performed on each block of data. As each iteration is conducted, gradually more and more errors are corrected until no further errors remain. In some real-time systems, the time dedicated to perform the iterations is limited and, thus, the decoding operation is stopped after several iterations, whether the data is error-free or not. This is one reason that it is important that the quality of the decoded data improve from one iteration to the next.
In addition to turbo-decoding, many practical systems use additional independent means to minimize the errors in the transmitted data. For example, in 3GPP standards for wireless communication, cyclic redundancy check (CRC) blocks are added to the transmitted data. The length of the CRC blocks may or may not coincide with the length of the turbo-decoder block. Each CRC block is attached at the end of a respective transport block. Subsequently, several such CRC blocks can be concatenated to form a code block.
Conventional methods of turbo-decoding only deal with cases where the coded frame contains a single CRC code block (where “block” means the original data and the CRC generated for the original data). For example, a device disclosed in U.S. Pat. No. 5,761,248, the disclosure of which is incorporated herein by reference for all it teaches, discloses a method for determining an adaptive abort criteria. Further, a device disclosed in U.S. Pat. No. 6,182,261, the disclosure of which is also incorporated herein by reference for all it teaches, stops the iteration process if the CRC check passes. Neither of the devices disclosed in these two patents addresses the situation where there is a plurality of CRC code words in the same coded data frame. Furthermore, the two patents mentioned do not describe how to handle, or even recognize, the situation where some of the CRC code words pass the CRC check and some of the CRC code words fail the CRC check.
FIG. 1 depicts a block diagram of a typical conventional turbo encoder (1). Data comprising a number of bits to be encoded enters the Interleaver (10) wherein the bits are intermixed in a pseudo-random manner. For example, a common method of interleaving is to form a matrix, e.g., writing into the matrix in rows and reading out from the matrix in columns, with a possible permutation of the row and/or column order being between the writing and the reading. At the same time data is input to the Interleaver (10), the same data bits are also input to the First RSC (Recursive Systematic Convolutional) Encoder block (11), from which a first parity bit is output for every input bit. The output of the Interleaver (10) enters a Second RSC Encoder block (12), where a second parity bit is generated. Thus all the parity bits are generated by recursive systematic convolutional encoders, which are commonly known.
MUX (13) alternately selects bits from the original data, i.e., the “Systematic” bits, and the two parity bits output respectively from the first and second RSC encoding blocks. Thus, for every bit at the input to the Turbo Encoder (1), each ofthree different bits are alternately output—a Systematic Bit, a First Parity Bit and a Second Parity Bit.
FIG. 2 shows a prior art implementation technique for a conventional turbo-decoder as explained, for example, in the references mentioned above.
In particular, a Systematic Bit and a First Parity Bit enter Decoder 1 (20). Additionally, extrinsic information for each bit, as calculated during the previous iteration, enters Decoder 1 (20) as well. The output of Decoder 1 (20) comprises a new extrinsic value for each input bit. For example, a “extrinsic” number comprises a digital representation of how likely the original data bit was a “0” or how likely the original data bit was a “1”. The range of values for the extrinsic number can be, for example, from −7 to +7. A “strong zero”, or in other words, a representation that the bit is most likely a “0” can be shown as −7 and a representation that the bit is most likely a “1” can be shown as +7, with varying degrees of “extrinsic” being represented by the numbers between −7 and +7.
As shown in FIG. 2, the new extrinsic value enters Interleaver (21), which is typically identical in function to Interleaver (10) shown in the Encoder of FIG. 1. Interleaver (21) performs any of a variety of different interleaving algorithms on the input data. The output from Interleaver (21), along with the Second Parity Bit, enters a second decoder, Decoder 2 (22). Decoder 2 (22) calculates a new extrinsic value based on the extrinsic value from Interleaver (21) together with the Second Parity Bit. The new extrinsic value from Decoder 2 (22) takes into account the former extrinsic value, i.e., from Decoder 1 (20), and the additional information (Second Parity Bit) to form a better estimate for the true value of the input data. Decoder 2 (22) then feeds its output to De-Interleaver (23), which feeds the de-interleaved extrinsic value back to Decoder 1 (20) for another iteration. Thus, the likelihood of “knowing”, and ultimately outputting, the correct value for the data bit, i.e., “1” or “0”, increases from iteration to iteration.
The output from De-Interleaver (23) also feeds a Hard Decision block (24), which translates the extrinsic information output from De-Interleaver (23) into a hard decision (i.e., “1” or “0”). The Hard Decision output is then presented to a CRC Check block (25), which uses a standard CRC checking algorithm to determine if the output sequence of hard decisions from Hard Decision block (24) is correct. If the CRC test fails, nothing can be done, except at the system level where it may be possible to request a complete retransmission of the data.
An entirely turbo-decoded block of data must be written into the Interleaver (21) before the output of Interleaver (21) can be fed to Decoder 2 (22). The reason for this is because the interleaving process is defined so that all (or almost all) input bits must be stored before the output bits can be generated. This is true for De-Interleaver (23) as well. Accordingly, the circuit works in two distinct phases, as follows:
Phase 1: through Decoder 1 (20) and output from Interleaver (21). In this phase, the data is in interleaved order and therefore the CRC cannot be checked.
Phase 2: through Decoder 2 (22) and out from De-Interleaver (23). Only in this phase can the CRC be checked.
Also, the length of a CRC block does not necessarily coincide with the length of the Turbo Decoder block.
FIG. 3 depicts an example for a single turbo-decoder block, which consists of three CRC units, each of which has a data block terminated by a CRC trailer.